#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pi;
inline int gin(){
    int s=0,f=1;
    char c=getchar();
    while(c<'0' || c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        s=(s<<3)+(s<<1)+(c^48);
        c=getchar();
    }
    return s*f;
}

const int mod=1e9+7;
int n,m,k,t,fib[32],fail[1000005];
string f[32];
char s[100005];
map<string,int> mp;

pi Fib(int n) {
    if(n< 0) return {0,0};
    if(n==0) return {0,1};
    pi p=Fib(n>>1);
    int c=p.first*((2*p.second-p.first+mod)%mod)%mod;
    int d=(p.first*p.first+p.second*p.second)%mod;
    if(n&1) return {d,c+d};
    else return {c,d};
}

inline void pre() {
	fail[1]=0;
	int j=0;
	for(int i=1;i<n;i++){
		while(j && s[j+1]!=s[i+1]) j=fail[j];
		if(s[j+1]==s[i+1]) j++;
		fail[i+1]=j;
	}
}

inline int kmp(string S) {
    int len=S.size();
    S=" "+S;
    int j=0,res=0;
    for(int i=0;i<len;i++) {
        while(j && s[j+1]!=S[i+1]) j=fail[j];
        if(s[j+1]==S[i+1]) j++;
        if(j==n) {
            res=(res+1)%mod;
            j=fail[j];
        }
    }
    return res%mod;
}

signed main(){
     freopen("brotherhood.in","r",stdin);
     freopen("brotherhood.out","w",stdout);
    fib[0]=0,fib[1]=1,f[1]="0",f[2]="1";
    for(int i=2;i<=31;i++) fib[i]=fib[i-1]+fib[i-2];
    for(int i=3;i<=31;i++) f[i]=f[i-1]+f[i-2];
    k=gin(),m=gin();
    if(k==1) {
        while(m--) {
            scanf("%s",s+1);
            if(s[1]=='0' && s[2]==0) puts("1");
            else puts("0");
        }
        return 0;
    }
    if(k==2) {
        while(m--) {
            scanf("%s",s+1);
            if(s[1]=='1' && s[2]==0) puts("1");
            else puts("0");
        }
        return 0;
    }
    while(m--) {
        scanf("%s",s+1);
        if(mp[s+1]) {
            printf("%I64d\n",mp[s+1]);
            continue;
        }
        n=strlen(s+1);
        pre();
        for(int i=2;i<=31;i++) if(fib[i]>n) {t=i; break;}
        if(t>=k) {
            printf("%I64d\n",kmp(f[k]));
            continue;
        }
        // if(t-1>k) {puts("0"); continue;}
        // else t--;
        // if(t>2) t--;
        // else t=1;
        string s1=f[t],s2=f[t+1];
        int a=kmp(s1),b=kmp(s2),ab=(kmp(s1+s2)-a-b+mod)%mod,ba=(kmp(s2+s1)-a-b+mod)%mod,bb=(kmp(s2+s2)-b-b+mod)%mod;
        int A=Fib(k-2-t+1).first,B=Fib(k-1-t+1).first;
        int AB=Fib(k-2-t+1).first+(((k-2-t+1>0) && (k-2-t+1)&1)?-1:0);
        int BA=A;
        int BB=Fib(k-3-t+1).first+(((k-3-t+1>0) && (k-3-t+1)&1)?-1:0);
        // printf("$ %lld $ \n",t);
        // cout<<s1<<" "<<s2<<" "<<s1+s2<<" "<<s2+s1<<" "<<s2+s2<<"\n";
        // printf("& %lld %lld %lld %lld %lld\n",a,b,ab,ba,bb);
        // printf("# %lld %lld %lld %lld %lld\n",A,B,AB,BA,BB);
        int ans=((a*A%mod+b*B%mod)%mod+(ab*AB%mod+ba*BA%mod)%mod+bb*BB%mod)%mod;
        mp[s+1]=ans;
        printf("%I64d\n",ans);
    }
    return 0;
}
